package mo.offer_special;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class L086 {

    private boolean[][] f;
    private List<List<String>> tmp = new ArrayList<>();
    private List<String> ans = new ArrayList<>();
    private int n;

    public String[][] partition(String s) {
        n = s.length();
        f = new boolean[n][n];

        for (int i = 0; i < n; i++) {
            Arrays.fill(f[i], true);
        }

        for (int i = n-1; i >= 0; i--) {
            for (int j = i+1; j < n; j++) {
                f[i][j] = (s.charAt(i) == s.charAt(j)) && f[i+1][j-1];
            }
        }

        dfs(s, 0);
        int rows = tmp.size();
        String[][] res = new String[rows][];
        for (int i = 0; i < rows; i++) {
            List<String> combination = tmp.get(i);
            res[i] = new String[combination.size()];
            for (int j = 0; j < combination.size(); j++) {
                res[i][j] = combination.get(j);
            }
        }

        return res;
    }

    private void dfs(String s, int i) {
        if (i == n) {
            tmp.add(new ArrayList<>(ans));
            return;
        }
        for (int j = i; j < n; j++) {
            if (f[i][j]) {
                ans.add(s.substring(i, j+1));
                dfs(s, j+1);
                ans.remove(ans.size()-1);
            }
        }
    }

}
